#ifndef DYNAMIC_BITSET_H
#define DYNAMIC_BITSET_H
// (C) Copyright Chuck Allison and Jeremy Siek 2001, 2002.
//
// Permission to copy, use, modify, sell and distribute this software
// is granted provided this copyright notice appears in all
// copies. This software is provided "as is" without express or
// implied warranty, and with no claim as to its suitability for any
// purpose.

// With optimizations, bug fixes, and improvements by Gennaro Prota.

// See http://www.boost.org/libs/dynamic_bitset for documentation.

// -------------------------------------
// CHANGE LOG:
//
// - corrected workaround for Dinkum lib's allocate() [GP]
// - changed macro test for old iostreams [GP]
// - removed #include <vector> for now. [JGS]
// - Added __GNUC__ to compilers that cannot handle the constructor from basic_string. [JGS]
// - corrected to_block_range [GP]
// - corrected from_block_range [GP]
// - Removed __GNUC__ from compilers that cannot handle the constructor
//     from basic_string and added the workaround suggested by GP. [JGS]
// - Removed __BORLANDC__ from the #if around the basic_string
//     constructor. Luckily the fix by GP for g++ also fixes Borland. [JGS]

#include <cassert>
#include <string>
#include <cstring>             // for memset, memcpy, memcmp, etc.
#include <algorithm>           // for std::swap, std::min, std::copy, std::fill
#include <memory>           // for std::swap, std::min, std::copy, std::fill
#include <stdlib.h>
#include "LogAssert.h"

namespace std
{
	typedef ::size_t size_t;
}
// (C) Copyright Chuck Allison and Jeremy Siek 2001, 2002.
//
// Permission to copy, use, modify, sell and distribute this software
// is granted provided this copyright notice appears in all
// copies. This software is provided "as is" without express or
// implied warranty, and with no claim as to its suitability for any
// purpose.

// With optimizations by Gennaro Prota.

    class dynamic_bitset_base
    {
      typedef std::size_t size_type;
    public:
#if defined(LINUX) && (defined (__LP64__) || defined(_AMD64_))
		typedef unsigned int Block;
#else
		typedef unsigned long Block;
#endif
      enum { bits_per_block = 8 * sizeof(Block) };

      dynamic_bitset_base()
        : m_bits(0), m_num_bits(0), m_num_blocks(0) { }

      dynamic_bitset_base(size_type num_bits) :
          m_num_bits(num_bits),
          m_num_blocks(calc_num_blocks(num_bits))
      {
      	if (m_num_blocks != 0)
      	{
	      	m_bits = new Block[m_num_blocks];	
   	     memset(m_bits, 0, m_num_blocks * sizeof(Block)); // G.P.S. ask to Jeremy
      	}
	      else
      		m_bits = 0;
      }
      ~dynamic_bitset_base() {
         delete []m_bits;;
      }

      Block* m_bits;
      size_type m_num_bits;
      size_type m_num_blocks;

      static size_type word(size_type bit)  { return bit / bits_per_block; } // [gps]
      static size_type offset(size_type bit){ return bit % bits_per_block; } // [gps]
      static Block mask1(size_type bit) { return Block(1) << offset(bit); }
      static Block mask0(size_type bit) { return ~(Block(1) << offset(bit)); }
      static size_type calc_num_blocks(size_type num_bits)
        { return (num_bits + bits_per_block - 1) / bits_per_block; }
    };


    // ------- count table implementation --------------

    typedef unsigned char byte_t;

    template <bool bogus = true>
    struct bitcount {
        typedef byte_t element_type;
        static const byte_t table[];

    };
    //typedef count<true> table_t;


    // the table: wrapped in a class template, so
    // that it is only instantiated if/when needed
    //
     template <bool bogus>
     const byte_t bitcount<bogus>::table[] =
     {
       // Automatically generated by GPTableGen.exe v.1.0
       //
     0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
     1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
     1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
     2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
     1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
     2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
     2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
     3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8
     };


    // -------------------------------------------------------
    template <typename BlockInputIterator>
    std::size_t initial_num_blocks(BlockInputIterator first,
                   BlockInputIterator last)
    {
      std::size_t n = 0;
      while (first != last)
        ++first, ++n;
      return n;
    }

class dynamic_bitset : public dynamic_bitset_base
{
	public:
	
    typedef Block block_type;
    typedef std::size_t size_type;
    enum { bits_per_block = 8 * sizeof(Block) };

    // reference to a bit
    class reference
    {
        friend class dynamic_bitset;
        dynamic_bitset* bs;
        size_type bit;
        reference(); // intentionally not implemented
        reference(dynamic_bitset& bs_, size_type bit_) : bs(&bs_), bit(bit_){ }
    public:
        reference& operator=(bool value)          // for b[i] = x
        {
            if (value)
                bs->set(bit);
            else
                bs->reset(bit);
            return *this;
        }
        reference& operator|=(bool value)         // for b[i] |= x
        {
            if (value)
                bs->set(bit);
            return *this;
        }
        reference& operator&=(bool value)         // for b[i] &= x
        {
            if (! (value && bs->test(bit)))
                bs->reset(bit);
            return *this;
        }
        reference& operator^=(bool value)         // for b[i] ^= x
        {
            bs->set(bit, bs->test(bit) ^ value);
            return *this;
        }
        reference& operator-=(bool value)         // for b[i] -= x
        {
            if (!value)
                bs->reset(bit);
            return *this;
        }
        reference& operator=(const reference& j)  // for b[i] = b[j]
        {
            if (j.bs->test(j.bit))
                bs->set(bit);
            else
                bs->reset(bit);
            return *this;
        }
        reference& operator|=(const reference& j) // for b[i] |= b[j]
        {
            if (j.bs->test(j.bit))
                bs->set(bit);
            return *this;
        }
        reference& operator&=(const reference& j) // for b[i] &= b[j]
        {
            if (! (j.bs->test(j.bit) && bs->test(bit)))
                bs->reset(bit);
            return *this;
        }
        reference& operator^=(const reference& j) // for b[i] ^= b[j]
        {
            bs->set(bit, bs->test(bit) ^ j.bs->test(j.bit));
            return *this;
        }
        reference& operator-=(const reference& j) // for b[i] -= b[j]
        {
            if (!j.bs->test(j.bit))
                bs->reset(bit);
            return *this;
        }
        bool operator~() const                    // flips the bit
        {
            return ! bs->test(bit);
        }
        operator bool() const                     // for x = b[i]
        {
            return bs->test(bit);
        }
        reference& flip()                         // for b[i].flip();
        {
            bs->flip(bit);
            return *this;
        }
    };
    typedef bool const_reference;

	dynamic_bitset ();
	   explicit
    dynamic_bitset(size_type num_bits, unsigned long value = 0);

    // The parenthesis around std::basic_string<CharT, Traits, Alloc>::npos
    // in the code below are to avoid a g++ 3.2 bug and a Borland bug. -JGS
    template <typename String>
    explicit
    dynamic_bitset(const String& s,
        typename String::size_type pos = 0,
        typename String::size_type n
            = (String::npos))
        : dynamic_bitset_base
            (std::min(n, s.size() - pos))
    {
        // Locate sub string
        AssertIf (pos > s.length());
        from_string(s, pos, std::min(n, s.size() - pos));
    }

    // The first bit in *first is the least significant bit, and the
    // last bit in the block just before *last is the most significant bit.
    template <typename BlockInputIterator>
    dynamic_bitset(BlockInputIterator first, BlockInputIterator last)
        : dynamic_bitset_base
            (initial_num_blocks(first, last)
            * bits_per_block)
    {
        if (first != last) {
            if (this->m_num_bits == 0) { // dealing with input iterators
                this->append(first, last);
            } else {
                // dealing with forward iterators, memory has been allocated
                for (std::size_t i = 0; first != last; ++first, ++i)
                    set_block_(i, *first);
            }
        }
    }


    // copy constructor
    dynamic_bitset(const dynamic_bitset& b);

    void swap(dynamic_bitset& b);

    dynamic_bitset& operator=(const dynamic_bitset& b);

    // size changing operations
    void resize(size_type num_bits, bool value = false);
    void clear();
    void push_back(bool bit);
    void append(Block block);

    // This is declared inside the class to avoid compiler bugs.
    template <typename BlockInputIterator>
    void append(BlockInputIterator first, BlockInputIterator last)
    {
        if (first != last) {
            std::size_t nblocks = initial_num_blocks(first, last);
            if (nblocks == 0) { // dealing with input iterators
                for (; first != last; ++first)
                    append(*first);
            } else { // dealing with forward iterators
                if (size() % bits_per_block == 0) {
                    std::size_t old_nblocks = this->m_num_blocks;
                    resize(size() + nblocks * bits_per_block);
                    for (std::size_t i = old_nblocks; first != last; ++first)
                        set_block_(i++, *first);
                } else {
                    // probably should optimize this,
                    // but I'm sick of bit twiddling
                    for (; first != last; ++first)
                        append(*first);
                }
            }
        }
    }


    // bitset operations
    dynamic_bitset& operator&=(const dynamic_bitset& b);
    dynamic_bitset& operator|=(const dynamic_bitset& b);
    dynamic_bitset& operator^=(const dynamic_bitset& b);
    dynamic_bitset& operator-=(const dynamic_bitset& b);
    dynamic_bitset& operator<<=(size_type n);
    dynamic_bitset& operator>>=(size_type n);
    dynamic_bitset operator<<(size_type n) const;
    dynamic_bitset operator>>(size_type n) const;

    // basic bit operations
    dynamic_bitset& set(size_type n, bool val = true);
    dynamic_bitset& set();
    dynamic_bitset& reset(size_type n);
    dynamic_bitset& reset();
    dynamic_bitset& flip(size_type n);
    dynamic_bitset& flip();
    bool test(size_type n) const;
    bool any() const;
    bool none() const;
    dynamic_bitset operator~() const;
    size_type count() const;

    // subscript
    reference operator[](size_type pos) { return reference(*this, pos); }
    bool operator[](size_type pos) const
	{
		#if UNITY_EDITOR
		if (pos < this->m_num_bits)
			return test_(pos);
		else
		{
			ErrorString("dynamic_bitset.test bit out of bounds");
			return false;
		}
		#else
		AssertIf(pos >= this->m_num_bits);
		return test_(pos);
		#endif
	}

    unsigned long to_ulong() const;

    size_type size() const;
    size_type num_blocks() const;

    bool is_subset_of(const dynamic_bitset& a) const;
    bool is_proper_subset_of(const dynamic_bitset& a) const;

    void m_zero_unused_bits();
    

private:
    void set_(size_type bit);
    bool set_(size_type bit, bool val);
    void reset_(size_type bit);
    bool test_(size_type bit) const;
    void set_block_(size_type blocknum, Block b);

public:

    // This is templated on the whole String instead of just CharT,
    // Traits, Alloc to avoid compiler bugs.
    template <typename String>
    void from_string(const String& s, typename String::size_type pos,
                     typename String::size_type rlen)
    {
        reset(); // bugfix [gps]
        size_type const tot = std::min (rlen, s.length()); // bugfix [gps]

        // Assumes string contains only 0's and 1's
        for (size_type i = 0; i < tot; ++i) {
        if (s[pos + tot - i - 1] == '1') {
                set_(i);
            } else {
            AssertIf(s[pos + tot - i - 1] != '0');
            }
        }
    }

};

// Global Functions:

// comparison
inline bool operator!=(const dynamic_bitset& a,
                const dynamic_bitset& b);

inline bool operator<=(const dynamic_bitset& a,
                const dynamic_bitset& b);

inline bool operator>(const dynamic_bitset& a,
               const dynamic_bitset& b);

inline bool operator>=(const dynamic_bitset& a,
                const dynamic_bitset& b);

// bitset operations
inline dynamic_bitset
operator&(const dynamic_bitset& b1,
          const dynamic_bitset& b2);

inline dynamic_bitset
operator|(const dynamic_bitset& b1,
          const dynamic_bitset& b2);

inline dynamic_bitset
operator^(const dynamic_bitset& b1,
          const dynamic_bitset& b2);

inline dynamic_bitset
operator-(const dynamic_bitset& b1,
          const dynamic_bitset& b2);


template <typename String>
void
to_string(const dynamic_bitset& b,
          String& s);

template <typename BlockOutputIterator>
void
to_block_range(const dynamic_bitset& b,
               BlockOutputIterator result);

template <typename BlockIterator>
inline void
from_block_range(BlockIterator first, BlockIterator last,
                 dynamic_bitset& result);


//=============================================================================
// dynamic_bitset implementation


//-----------------------------------------------------------------------------
// constructors, etc.

inline dynamic_bitset::dynamic_bitset()
  : dynamic_bitset_base(0) { }

inline dynamic_bitset::
dynamic_bitset(size_type num_bits, unsigned long value)
  : dynamic_bitset_base(num_bits)
{
  const size_type M = std::min(sizeof(unsigned long) * 8, num_bits);
  for(size_type i = 0; i < M; ++i, value >>= 1) // [G.P.S.] to be optimized
    if ( value & 0x1 )
      set_(i);
}

// copy constructor
inline dynamic_bitset::
dynamic_bitset(const dynamic_bitset& b)
  : dynamic_bitset_base(b.size())
{
    memcpy(this->m_bits, b.m_bits, this->m_num_blocks * sizeof(Block));
}

inline void dynamic_bitset::
swap(dynamic_bitset& b)
{
    std::swap(this->m_bits, b.m_bits);
    std::swap(this->m_num_bits, b.m_num_bits);
    std::swap(this->m_num_blocks, b.m_num_blocks);
}

inline dynamic_bitset& dynamic_bitset::
operator=(const dynamic_bitset& b)
{
    dynamic_bitset tmp(b);
    this->swap(tmp);
    return *this;
}

//-----------------------------------------------------------------------------
// size changing operations

inline void dynamic_bitset::
resize(size_type num_bits, bool value)
{
  if (num_bits == size())
    return;
  if (num_bits == 0)
  {
  this->m_num_bits = 0;
  this->m_num_blocks = 0;
  delete this->m_bits;
  this->m_bits = 0;
  return;
  }
  size_type new_nblocks = this->calc_num_blocks(num_bits);
  Block* d = new Block[new_nblocks];
  if (num_bits < size()) { // shrink
    std::copy(this->m_bits, this->m_bits + new_nblocks, d);
    std::swap(d, this->m_bits);
    delete []d;
  } else { // grow
    std::copy(this->m_bits, this->m_bits + this->m_num_blocks, d);
    Block val = value? ~static_cast<Block>(0) : static_cast<Block>(0);
    std::fill(d + this->m_num_blocks, d + new_nblocks, val);
    std::swap(d, this->m_bits);
    for (std::size_t i = this->m_num_bits;
         i < this->m_num_blocks * bits_per_block; ++i)
      set_(i, value);
    if (d != 0)
      delete []d;
  }
  this->m_num_bits = num_bits;
  this->m_num_blocks = this->calc_num_blocks(num_bits);
  m_zero_unused_bits();
}

inline void dynamic_bitset::
clear()
{
  if (this->m_bits != 0) {
    delete this->m_bits;
    this->m_bits = 0;
    this->m_num_bits = 0;
    this->m_num_blocks = 0;
  }
}


inline void dynamic_bitset::
push_back(bool bit)
{
  this->resize(this->size() + 1);
  set_(this->size() - 1, bit);
}

inline void dynamic_bitset::
append(Block value)
{
  std::size_t old_size = size();
  resize(old_size + bits_per_block);
  if (size() % bits_per_block == 0)
    set_block_(this->m_num_blocks - 1, value);
  else {
      // G.P.S. to be optimized
    for (std::size_t i = old_size; i < size(); ++i, value >>= 1)
      set_(i, value & 1);
  }
}


//-----------------------------------------------------------------------------
// bitset operations
inline dynamic_bitset&
dynamic_bitset::operator&=(const dynamic_bitset& rhs)
{
    AssertIf(size() != rhs.size());
    for (size_type i = 0; i < this->m_num_blocks; ++i)
        this->m_bits[i] &= rhs.m_bits[i];
    return *this;
}

inline dynamic_bitset&
dynamic_bitset::operator|=(const dynamic_bitset& rhs)
{
    AssertIf(size() != rhs.size());
    for (size_type i = 0; i < this->m_num_blocks; ++i)
        this->m_bits[i] |= rhs.m_bits[i];
    m_zero_unused_bits();
    return *this;
}

inline dynamic_bitset&
dynamic_bitset::operator^=(const dynamic_bitset& rhs)
{
    AssertIf(size() != rhs.size());
    for (size_type i = 0; i < this->m_num_blocks; ++i)
        this->m_bits[i] ^= rhs.m_bits[i];
    m_zero_unused_bits();
    return *this;
}

inline dynamic_bitset&
dynamic_bitset::operator-=(const dynamic_bitset& rhs)
{
    AssertIf(size() != rhs.size());
    for (size_type i = 0; i < this->m_num_blocks; ++i)
        this->m_bits[i] = this->m_bits[i] & ~rhs.m_bits[i];
    m_zero_unused_bits();
    return *this;
}

inline dynamic_bitset&
dynamic_bitset::operator<<=(size_type n)
{
    if (n >= this->m_num_bits)
        return reset();
    //else
    if (n > 0)
    {
        size_type  const last  = this->m_num_blocks - 1; // m_num_blocks is >= 1
        size_type  const div   = n / bits_per_block; // div is <= last
        size_type  const r     = n % bits_per_block;

        // PRE: div != 0  or  r != 0

        if (r != 0) {

            block_type const rs = bits_per_block - r;

            for (size_type i = last-div; i>0; --i) {
                this->m_bits[i+div] = (this->m_bits[i] << r) | (this->m_bits[i-1] >> rs);
            }
            this->m_bits[div] = this->m_bits[0] << r;

        }
        else {
            for (size_type i = last-div; i>0; --i) {
                this->m_bits[i+div] = this->m_bits[i];
            }
            this->m_bits[div] = this->m_bits[0];
        }


        // div blocks are zero filled at the less significant end
        std::fill(this->m_bits, this->m_bits+div, static_cast<block_type>(0));


    }

    return *this;


}







// NOTE: this assumes that within a single block bits are
//       numbered from right to left. G.P.S.
//
//      static Block offset(size_type bit)
//        { return  bit % bits_per_block; }
//
//
// In the implementation below the 'if (r != 0)' is logically
// unnecessary. It's there as an optimization only: in fact
// for r==0 the first branch becomes the second one with the
// b[last-div] = b[last] >> r; statement that does the work of
// the last iteration.
//
inline
dynamic_bitset & dynamic_bitset::operator>>=(size_type n) {
    if (n >= this->m_num_bits) {
        return reset();
    }
    //else
    if (n>0){

        size_type  const last  = this->m_num_blocks - 1; // m_num_blocks is >= 1
        size_type  const div   = n / bits_per_block; // div is <= last
        size_type  const r     = n % bits_per_block;

        // PRE: div != 0  or  r != 0

        if (r != 0) {

            block_type const ls = bits_per_block - r;

            for (size_type i = div; i < last; ++i) {
                this->m_bits[i-div] = (this->m_bits[i] >> r) | (this->m_bits[i+1]  << ls);
            }
            // r bits go to zero
            this->m_bits[last-div] = this->m_bits[last] >> r;
        }

        else {
            for (size_type i = div; i <= last; ++i) {
                this->m_bits[i-div] = this->m_bits[i];
            }
            // note the '<=': the last iteration 'absorbs'
            // this->m_bits[last-div] = this->m_bits[last] >> 0;
        }



        // div blocks are zero filled at the most significant end
        std::fill(this->m_bits+(this->m_num_blocks-div), this->m_bits+this->m_num_blocks, static_cast<block_type>(0));
    }

    return *this;
}







inline dynamic_bitset
dynamic_bitset::operator<<(size_type n) const
{
    dynamic_bitset r(*this);
    return r <<= n;
}

inline  dynamic_bitset
dynamic_bitset::operator>>(size_type n) const
{
    dynamic_bitset r(*this);
    return r >>= n;
}


//-----------------------------------------------------------------------------
// basic bit operations

inline dynamic_bitset&
dynamic_bitset::set(size_type pos, bool val)
{
    AssertIf(pos >= this->m_num_bits);
    set_(pos, val);
    return *this;
}

inline dynamic_bitset&
dynamic_bitset::set()
{
  if (this->m_num_bits > 0) {
    using namespace std;
    memset(this->m_bits, ~0u, this->m_num_blocks * sizeof(this->m_bits[0]));
    m_zero_unused_bits();
  }
  return *this;
}

inline dynamic_bitset&
dynamic_bitset::reset(size_type pos)
{
    AssertIf(pos >= this->m_num_bits);
    reset_(pos);
    return *this;
}

inline dynamic_bitset&
dynamic_bitset::reset()
{
  if (this->m_num_bits > 0) {
    using namespace std;
    memset(this->m_bits, 0, this->m_num_blocks * sizeof(this->m_bits[0]));
  }
  return *this;
}

inline dynamic_bitset&
dynamic_bitset::flip(size_type pos)
{
    AssertIf(pos >= this->m_num_bits);
    this->m_bits[this->word(pos)] ^= this->mask1(pos);
    return *this;
}

inline dynamic_bitset&
dynamic_bitset::flip()
{
    for (size_type i = 0; i < this->m_num_blocks; ++i)
        this->m_bits[i] = ~this->m_bits[i];
    m_zero_unused_bits();
    return *this;
}

inline bool dynamic_bitset::test(size_type pos) const
{
	#if UNITY_EDITOR
	if (pos < this->m_num_bits)
		return test_(pos);
	else
	{
		ErrorString("dynamic_bitset.test bit out of bounds");
		return false;
	}
	#else
    AssertIf(pos >= this->m_num_bits);
    return test_(pos);
	#endif
}

inline bool dynamic_bitset::any() const
{
    for (size_type i = 0; i < this->m_num_blocks; ++i)
        if (this->m_bits[i])
            return 1;
    return 0;
}

inline bool dynamic_bitset::none() const
{
    return !any();
}

inline dynamic_bitset
dynamic_bitset::operator~() const
{
    dynamic_bitset b(*this);
    b.flip();
    return b;
}


/* snipped: [gps]

The following is the straightforward implementation of count(), which
we leave here in a comment for documentation purposes.

template <typename Block, typename Allocator>
typename dynamic_bitset::size_type
dynamic_bitset::count() const
{
    size_type sum = 0;
    for (size_type i = 0; i != this->m_num_bits; ++i)
        if (test_(i))
            ++sum;
    return sum;
}

The actual algorithm used is based on using a lookup
table.


  The basic idea of the method is to pick up X bits at a time
  from the internal array of blocks and consider those bits as
  the binary representation of a number N. Then, to use a table
  of 1<<X elements where table[N] is the number of '1' digits
  in the binary representation of N (i.e. in our X bits).

  Note that the table can be oversized (i.e. can even have more
  than 1<<X elements; in that case only the first 1<<X will be
  actually used) but it cannot be undersized.
  In this implementation X is 8 (but can be easily changed: you
  just have to change the definition of count<>::max_bits) and
  the internal array of blocks is seen as an array of bytes: if
  a byte has exactly 8 bits then it's enough to sum the value
  of table[B] for each byte B. Otherwise 8 bits at a time are
  'extracted' from each byte by using another loop. As a further
  efficiency consideration note that even if you have, let's say,
  32-bit chars the inner loop will not do 4 (i.e. 32/8) iterations,
  unless you have at least one bit set in the highest 8 bits of the
  byte.

  Note also that the outmost if/else is not necessary but is there
  to help the optimizer (and one of the two branches is always dead
  code).

  Aras: hardcoded table to be always max_bits=8. To help not so good compilers.

*/


inline dynamic_bitset::size_type
dynamic_bitset::count() const
{
    const byte_t * p = reinterpret_cast<const byte_t*>(this->m_bits);
    const byte_t * past_end = p + this->m_num_blocks * sizeof(Block);

    size_type num = 0;

    while (p < past_end) {
        num += bitcount<>::table[*p];
        ++p;
    }

    return num;
}


//-----------------------------------------------------------------------------
// conversions

// take as ref param instead?
template <typename CharT, typename Alloc>
void
to_string(const dynamic_bitset& b,
          std::basic_string<CharT, Alloc>& s)
{
    s.assign(b.size(), '0');
    for (std::size_t i = 0; i < b.size(); ++i)
        if (b.test(i)) // [G.P.S.]
            s[b.size() - 1 - i] = '1';
}


// Differently from to_string this function dumps out
// every bit of the internal representation (useful
// for debugging purposes)
//
template <typename CharT, typename Alloc>
void
dump_to_string(const dynamic_bitset& b,
               std::basic_string<CharT, Alloc>& s)
{
    std::size_t const len = b.m_num_blocks * (dynamic_bitset::bits_per_block);
    s.assign(len, '0');
    for (std::size_t i = 0; i != len; ++i)
      if (b[i])// could use test_ here, but we have friend issues.-JGS
            s[len - 1 - i] = '1';
}



template <typename BlockOutputIterator>
void
to_block_range(const dynamic_bitset& b,
               BlockOutputIterator result)
{
    AssertIf(!(b.size() != 0 || b.num_blocks() == 0));
    std::copy (b.m_bits, b.m_bits + b.m_num_blocks, result);
}

template <typename BlockIterator>
inline void
from_block_range(BlockIterator first, BlockIterator last,
                 dynamic_bitset& result)
{
    AssertIf(std::distance(first, last) != result.num_blocks());
    std::copy (first, last, result.m_bits);
    result.m_zero_unused_bits ();
}

inline dynamic_bitset::size_type
dynamic_bitset::size() const
{
    return this->m_num_bits;
}

inline dynamic_bitset::size_type
dynamic_bitset::num_blocks() const
{
    return this->m_num_blocks;
}

inline bool dynamic_bitset::
is_subset_of(const dynamic_bitset& a) const
{
    AssertIf(this->size() != a.size());
    for (size_type i = 0; i < this->m_num_blocks; ++i)
        if (this->m_bits[i] & ~a.m_bits[i])
            return false;
    return true;
}

inline bool dynamic_bitset::
is_proper_subset_of(const dynamic_bitset& a) const
{
    AssertIf(this->size() != a.size());
    bool proper = false;
    for (size_type i = 0; i < this->m_num_blocks; ++i) {
        Block bt = this->m_bits[i], ba = a.m_bits[i];
        if (ba & ~bt)
            proper = true;
        if (bt & ~ba)
            return false;
    }
    return proper;
}

//-----------------------------------------------------------------------------
// comparison

inline bool operator==(const dynamic_bitset& a,
                const dynamic_bitset& b)
{
    using namespace std;
    return (a.m_num_bits == b.m_num_bits) &&
      ((a.m_num_bits == 0) ||
        !memcmp(a.m_bits, b.m_bits, a.m_num_blocks * sizeof(a.m_bits[0])));
}

inline bool operator!=(const dynamic_bitset& a,
                       const dynamic_bitset& b)
{
    return !(a == b);
}

inline bool operator<(const dynamic_bitset& a,
               const dynamic_bitset& b)
{
    AssertIf(a.size() != b.size());
    typedef dynamic_bitset::size_type size_type;

    if (a.size() == 0)
      return false;

    // Since we are storing the most significant bit
    // at pos == size() - 1, we need to do the memcmp in reverse.

    // Compare a block at a time
    for (size_type i = a.m_num_blocks - 1; i > 0; --i)
      if (a.m_bits[i] < b.m_bits[i])
        return true;
      else if (a.m_bits[i] > b.m_bits[i])
        return false;

    if (a.m_bits[0] < b.m_bits[0])
      return true;
    else
      return false;
}

inline bool operator<=(const dynamic_bitset& a,
                       const dynamic_bitset& b)
{
    return !(a > b);
}

inline bool operator>(const dynamic_bitset& a,
                      const dynamic_bitset& b)
{
    AssertIf(a.size() != b.size());
    typedef dynamic_bitset::size_type size_type;

    if (a.size() == 0)
      return false;

    // Since we are storing the most significant bit
    // at pos == size() - 1, we need to do the memcmp in reverse.

    // Compare a block at a time
    for (size_type i = a.m_num_blocks - 1; i > 0; --i)
      if (a.m_bits[i] < b.m_bits[i])
        return false;
      else if (a.m_bits[i] > b.m_bits[i])
        return true;

    if (a.m_bits[0] > b.m_bits[0])
      return true;
    else
      return false;
}

inline bool operator>=(const dynamic_bitset& a,
                       const dynamic_bitset& b)
{
    return !(a < b);
}

//-----------------------------------------------------------------------------
// bitset operations

inline dynamic_bitset
operator&(const dynamic_bitset& x,
          const dynamic_bitset& y)
{
    dynamic_bitset b(x);
    return b &= y;
}

inline dynamic_bitset
operator|(const dynamic_bitset& x,
          const dynamic_bitset& y)
{
    dynamic_bitset b(x);
    return b |= y;
}

inline dynamic_bitset
operator^(const dynamic_bitset& x,
          const dynamic_bitset& y)
{
    dynamic_bitset b(x);
    return b ^= y;
}

inline dynamic_bitset
operator-(const dynamic_bitset& x,
          const dynamic_bitset& y)
{
    dynamic_bitset b(x);
    return b -= y;
}


//-----------------------------------------------------------------------------
// private member functions

inline void dynamic_bitset::
set_(size_type bit)
{
    this->m_bits[this->word(bit)] |= this->mask1(bit);
}

inline void dynamic_bitset::
set_block_(size_type blocknum, Block value)
{
    this->m_bits[blocknum] = value;
}

inline void dynamic_bitset::
reset_(size_type b)
{
    this->m_bits[this->word(b)] &= this->mask0(b);
}

inline bool dynamic_bitset::test_(size_type b) const
{
    return (this->m_bits[this->word(b)] & this->mask1(b)) != static_cast<Block>(0);
}

inline bool dynamic_bitset::set_(size_type n, bool value)
{
    if (value)
        set_(n);
    else
        reset_(n);
    return value != static_cast<Block>(0);
}


// If size() is not a multiple of bits_per_block
// then not all the bits in the last block are used.
// This function resets the unused bits (convenient
// for the implementation of many member functions)
//
inline void dynamic_bitset::m_zero_unused_bits()
{
    AssertIf (this->m_num_blocks != this->calc_num_blocks(this->m_num_bits));

    // if != 0 this is the number of bits used in the last block
    const size_type used_bits = this->m_num_bits % bits_per_block;

    if (used_bits != 0)
        this->m_bits[this->m_num_blocks - 1] &= ~(~static_cast<Block>(0) << used_bits);

}

#endif
